Rekurziós agytorna
Ezúttal nézegetünk egy kis rekurziót, ha már múltkor belemelegedtünk az ilyen állásinterjús kérdésekbe. Mindenekelőtt a rekurzióról egy nagyon jó rövid oktatóvideót találtok itt, érdemes mindenkinek megnézni, aki esetleg még idegenkedne a történettől. Nagy vonalakban annyi a lényege, hogy a függvény saját magát hívja meg futtatása során, minden meghívás során egy új értéket átadva a következő lépésnek. Bizonyos esetekben helyettesítheti a hagyományos programozási módszereket, tisztább, egyszerűbb kódolást tesz lehetővé, azonban vigyázni is kell vele, mivel a stack túlcsordulását okozhatjuk. Persze az is fontos, hogy lefixáljuk, hogy meddig fusson a játék, ami nem meglepő, hiszen egy örökké tartó (vagyis a stack megteléséig tartó) futásban találhatjuk magunkat. A rekurzió működéséi elvét a fenti linken található videó nagyon jól elmagyarázza. Lényeg, hogy minden meghívás során a függvény és visszadott értéke a stackbe kerül, egészen pontosan az eggyel korábbi lépésben lefuttatott lépés fölé, hogy aztán a folyamat egy későbbi részében az értékét átadjuk a hívó félnek. Jajj, ez kicsit bonyolultnak hangzik, pedig tényleg nem az. Mivel a fenti videóban van egy tök jó példa is, most ezt az alap szintet átugorjuk és fejest ugrunk egy fokkal megbonyolított történetbe.
A játék a coin challenge nevet viseli, sokszor elő szokott bukkanni interjúkon. Lényege, hogy van megadott típusú fémpénzed (alábbi példában 1 ft-os és 2 ft-os), aminek kombinációival ki kell adnod egy adott összeget (alábbi példában 4-et). Kérdés, hogy hány féle variációja létezik? A konkrét példában 3 lesz a válasz, hiszen:
- 1+1+1+1 = 4
- 2+1+1 = 4
- 2+2 = 4
Nézzük csak a mellékelt kódot! Jujj de bonyinak tűnik, pedig ha megértjük a logikáját, nem lesz az! Van először is a main metódus, ez eléggé tiszta, meghívjuk a calculateCombo eljárásunkat, és átadjuk neki a kétféle forint típust (1-est és 2-est), valamint a végösszeget (4). Van még egy 0 értékű paraméter is, a lényege az, hogy induláskor az array első elemét, az 1 ft-os értékét jelezzük a programunknak vele, meg fogjuk érteni később a logikáját. Az a fontos, hogy azt lássuk, hogy ha a totalAmount értéket nem kezeljük le a programunkban, akkor a végeredmény nem lesz jó (5 lesz 3 helyett), mivel a 2+1+1 megoldás úgy is felírható, hogy 1+2+2, vagy 1+1+2. Igazából mindegyik jó, de nekünk a végeredmény szempontjából a forintok sorrendje lényegtelen.
Oké, nézzük a calculateCombo-t. Van egy combos nevű változónk 0 kezdőértékkel, ebbe fogjuk beletenni a sikeres futások számát, azaz minden sikeres futás esetén 1-el növeljük az értékét. Sikeres futás az, ha az amount értéke 0 lesz, azaz a folyamat során ha kivonunk a 4-ből mondjuk 1-et, a következő lépésben is 1-et, aztán még 1-et, az utolsó lépésben is 1-et, akkor megkapjuk az ötödik lépésben a 0 amount értéket. Ez esetben 1-el növeljük a combos értékét. Ha mondjuk az utolsó előtti lépésben 2-t vonnánk ki, akkor -1-et kapnánk, az ugye nem jó, azt az ágat ugorjuk is a return 0 átadásával.
Csinálunk egy for ciklust, amiben 2 lépést fogunk megtenni, első körben a coins array első elemét, az 1 ft-ost futtatjuk le, majd a folyamat későbbi szakaszában a 2 ft-os értéket. Itt jön képbe a currentIndex értéke, amelyet a későbbi lépésekben 0-ról 1-re állítunk (azaz 1 ft-osról 2 ft-osra), hogy még véletlenül se próbálkozzon a program újra az 1 ft-ossal. Mindjárt mutatok egy ábrát, ami alapján jól meg lehet ezt érteni, hogy miért is jó ez nekünk.
- 1. lépés: 0,4,0. Azaz elindítjuk a calculateCombo-t első körben, átadjuk neki a 0-s coin-t (azaz 1 ft-ost), a 4-es amount értéket (azaz induláskor még 4 ft-nál tartunk a 0-ig történő kivonásoknál), és a 0-s currentIndex-et (azaz jelezzük, hogy az 1 ft-ot vizsgáljuk, ez persze szorosan összefügg az első paraméterrel, a kettő értéke ugyanaz lesz minden lépésnél). Szóval az első lépésben átadjuk ezeket a paramétereket, elsőként megvizsgálja a program, hogy az amount értéke 0 lesz-e. Mivel nem, ezért megyünk tovább, mivel nem kisebb mint 0 az amount értéke, megyünk tovább, és eljutunk a for ciklusig. Itt meghívjuk a calculateCombo következő lépését, átadva neki a 0-s coint (1 ft-ost), a 4-1, azaz 3-as amount értéket, illetve továbbra is a 0-s értéket (mivel még a for ciklus első lépésénél vagyunk, azaz az 1 ft-ost vizsgáljuk).
- 2. lépés: 0,3,0. Az első lépés végén tehát a for ciklusban átadtuk ezeket a paremétereket. Mivel továbbra is nagyobb 0-nál az amount értéke, megyünk a for ciklushoz, ahol újra a for ciklus első lépését követjük el (és nem a másodikat, ez egy olyan pont, ami nem mindig egyértelmű, amikor az ember először találkozik ezzel a feladattal). Megívjuk a calculateCombo-t újra, ezúttal 0 coin értékkel (1 ft), 3-1 = 2 amount érékkel, és továbbra is 1 ft-al (azaz 0 értékkel).
- 3-5. lépés: és így megyünk tovább, egészen addig, amíg az amount értéke 0 lesz. Szuper, máris a combos értékét emeljük 1-el! Meg is állunk a return 1-nél, és nem megyünk tovább a for ciklusig, a stack-ből ki is kerül ez a lépés, visszalépünk 1-et a stack-ben, egészen a 4. lépésig.
- 6. lépés: a 4. lépéshez visszatérve a for ciklus második lépése fog lefutni, ezúttal úgy, hogy a calculateCombo-t 1 (azaz 2 ft), 1-2 (azaz -1), valamint 1 (azaz 2 ft) értékkel hívjuk meg. Itt figyeljük meg azt, hogy a currentIndex értéke 1-esre változott, ami a későbbi lépésekben már nem is fog tudni 0-ra visszatérni. Mivel a for ciklusban minden további lépésben a currentIndex értékénél kezdjük a ciklus lépéseit (azaz innentől 1-től), ez azt eredményezi, hogy a további lépésekben a 0-t (azaz 1 ft-ot) már nem fogjuk vizsgálni. Ez azért lesz jó nekünk, mert így megelőzzük a fölösleges köröket, és végeredményként nem 5-öt kapunk majd, hanem 3-at. Mindjárt megértitek miért. Szóval a 6. lépésben megkapta a calculateCombo az 1, -1, 1 értéket, mivel az amount értéke kisebb mint 0, a for ciklusig nem jutunk el, hanem 0 értékkel befejezzük a lépés futását, a stack-ben is törlődik ez a lépés, majd visszalépünk egyet a stack-ben, a 3. lépésig.
- 7. lépés: a 3. lépés for ciklusának 2. köre következik, a calculateCombo-t meghívjuk 1, 2-2 = 0, 1 értékekkel. Mivel az amount = 0, ezért ez is egy sikeres lépés volt, emeljük a combos értékét 1-el. A stack-ből is törlődik ez a lépés, illetve a 3. lépés is, mivel annak mindkét for ágán már végigmentünk, így visszamegyünk a 2. lépésig.
- 8. lépés: itt 1, 3-2 = 1, 1 értékeket kaptunk, így megyünk a for ciklusig. Mivel korábban a currentIndex megkapta az 1-es értéket, ezért itt már csak egyszer fut le a for ciklus, 2 ft-al. Tehát meghívjuk a calculateCombo-t 1, 1-2 = -1, 1 értékekkel.
- 9. lépés: mivel -1 értéket kaptunk, ezért ez az ág is sztornó, a stack-ből törlődik, visszalépünk a 8. lépésig. Mivel ott a for ciklusnak csak egyszer kellett lefutnia, a stack-ből az is törlődik, visszalépünk a 2. lépésig, aminek szintén végigfutott a for ciklusa, így a stack-ből az is kikerül, visszajutunk hát az 1. lépésig.
- 10. lépés: az első lépés for ciklusának 2. lépése fut le 1, 4-2 = 2, 1 értékekkel. Mivel az amount = 2, megyünk a for ciklusig, ahol currentIndex 1-es értéke miatt csak a 2. kör fut le 1, 2-2 = 0, 1 értékekkel.
- 11. lépés: és eljutottunk az utolsó lépésig, mivel az amount értéke 0, a combos értékét növeljük 1-el és 3-at kapunk.
Innen nincs tovább, a stack-ből szépen minden lépés kikerül, a folyamat a végére jutott. Szóval ennyi volt, tényleg nem egy nagy ördőngősség, egyszer kell csak megérteni a folyamatot, onnantól kezdve nem lesz baj az ehhez hasonló feladatokkal.
